МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
Кафедра САПР
Звіт
до
Лабораторної роботи №2
на тему:
СКІНЧЕННІ АВТОМАТИ
з курсу:
«Лінгвістичне забезпечення САПР»
1. МЕТА РОБОТИ
Навчитися моделювати роботу розпізнавача за допомогою скінченного автомата.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
В основі побудові компіляторів лежить теорія автоматів. Автомат – це нереально існуючий пристрій, а деяка математична модель, властивості і поведінку якої можна вивчити і яку можна імітувати на реальній ЕОМ.
Скінченний автомат – це найпростіша з моделей теорії автоматів.
Скінченним називається автомат, у якому множина внутрішніх станів і множина вхідних значень є скінченними множинами.
Скінченний розпізнавач – це модель пристрою із скінченним числом станів, які відрізняють правильно утворенні ланцюжки символів від неправильних (недопустимих).
Вхідна стрічка – це послідовність комірок, кожна комірка містить тільки один символ із скінченного вхідного алфавіту. Крайню ліву і крайню праву комірки можуть займати кінцеві маркери.
Вхідна головка у кожний момент часу читає одну вхідну комірку.
Пам'ять розпізнавача – це будь-яке сховище інформації або даних. Оскільки алфавіт скінченний, то об’єм пам’яті скінченний.
Керуючий пристрій є ядром розпізнавача. Це програма, яка керує роботою (поведінкою) розпізнавача. Керуючий пристрій – це скінченна множина станів разом з відображенням, яке описує як змінюється стани відповідно до поточного вхідного символу та інформацією, добутою із пам’яті.
Роботу розпізнавача можна відобразити в термінах його конфігурації:
1. Стан керуючого пристрою;
2. Вміст вхідної стрічки і положення вхідної головки;
3. Вміст пам’яті;
Конфігурація є початковою, якщо керуючий пристрій знаходиться у заданому початковому стані, вхідна головка може читати крайній лівий символ у стрічці і пам'ять має наперед установленний вміст.
Конфігурація є кінцевою, якщо керуючий пристрій знаходиться в одному з наперед визначених множиною кінцевих станів, а вхідна головка може читати правий кінцевий маркер, або вразі його відсутності, вона зійшла з правого кінця вхідної стрічки.
Формально скінченний розпізнавач визначається за п’ятьма характеристиками:
1. Скінченною множиною станів ;
2. Скінченним вхідним алфавітом ;
3. Множиною переходів , які відображають поведінку керуючого пристрою;
4. Початковим станом ;
5. Множиною кінцевих станів .
Тобто скінченний автомат описується як .
ПРИКЛАД ПОБУДОВИ СКІНЧЕННОГО АВТОМАТА
Прикладом скінченного автомата може контролер непарності «1» в ланцюжку символів, що складається з нулів і одиниць. Скінченний автомат буде допускати усі ланцюжки, які містять непарну кількість «1» і відкидати ті з них, які містять парну кількість «1».
Вхідним алфавітом такого автомата буде множина {0, 1}.
Множина станів буде складатись із двох станів ПАР і НЕПАР.
Початковим станом буде стан ПАР.
При читанні наступного вхідного символу стан автомата змінюється. Новий його стан залежить від вхідного символу і поточного символу.
Функція переходів буде мати такий вигляд:
(ПАР, 0)=ПАР
(ПАР, 1)=НЕПАР
(НЕПАР, 0)=НЕПАР
(НЕПАР, 1)=ПАР
Кінцевий (допускаючим) станом є НЕПАР.
Ланцюжок 1101 допускається автоматом, оскільки останнім є допускаючий стан НЕПАР. Іншою є ситуація при обробці ланцюжка 101, він відкидається, оскільки його кінцевим станом є недопустимий стан ПАР.
Один із зручних методів подання скінченного автомата є таблиця переходів.
Правила побудови таблиці такі:
1. Стовпці помічено символами вхідного алфавіту.
2. Рядки помічено символами станів.
3. Елементи таблиці є символами нових станів, які визначаються вхідним символом і попереднім станом.
4. Перший рядок помічено символом початкового стану.
5. Рядки, які відповідають допускаючим станам, помічені справа одиницями: рядки, які відкидаються автоматом, помічаються справа нулями.
Для нашого автомата таблиця переходів показана на рис. 1.
Крім табличного подання, скінченний автомат можна подати діаграмою (або графом) переход...